#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class PermutationAndCombination{
public:
    bool show = false;

    vector<int> data;
    int cnt = 0;

    // 取k个全排列
    int permutation(vector<int>& v, int k) {
        this->data = v;
        cnt = 0;

        permutation(0, k);
        return cnt;
    }

    // 全排列
    int permutation(vector<int>& v) {
        return permutation(v, v.size());
    }

    void permutation(int cur, int k) {
        if (cur == k) {
            if (show) {
                printV(data, k);
            }
            cnt ++; // 一种排列
            return;
        }

        for (int i = cur ; i < data.size() ; i++) {
            swap(data[i], data[cur]);
            permutation(cur+1, k);
            swap(data[i], data[cur]);
        }
    }

    // 全排列，去重
    int permutationUnique(vector<int>& v) {
        return permutationUnique(v, v.size());
    }


    // 取k个全排列，去重
    int permutationUnique(vector<int>& v, int k) {
        this->data = v;
        cnt = 0;

        std::sort(v.begin(), v.end());

        permutationUnique(0, k);
        return cnt;
    }

    void permutationUnique(int cur, int k) {
        if (cur == k) {
            if (show) {
                printV(data, k);
            }
            cnt ++;
            return;
        }

        for (int i = cur ; i < data.size() ; i++) {
            if (i > cur && willRepeat(cur, i)) 
                continue;
            swap(data[i], data[cur]);
            permutationUnique(cur+1, k);
            swap(data[i], data[cur]);

        }
        // 
    }
    bool willRepeat(int cur, int i) {
        for (int m = cur ; m < i ; m ++) {
            if (data[m] == data[i])
                return true;
        }
        return false;
    }

    // 取k个组合
    int combination(vector<int>& v, int k) {
        this->data = v;
        cnt = 0;

        sort(v.begin(), v.end());

        combination(0, 0, k);

        return cnt;
    }

    // cur: 当前位置
    // lower: 从#lower后面(包括)选下一个元素
    // 从data[lower]开始获得的组合
    void combination(int cur, int lower, int k) {
        // 下一个元素从[lower,$]中选
        if (cur == k) {
            if (show)
                printV(data, k);
            cnt ++; // 一个组合
            return;
        }

        if (lower > data.size())
            return;
        
        for (int i = lower ; i < data.size() ; i++) {
            swap(data[i], data[cur]);
            combination(cur+1, i+1, k);
            swap(data[i], data[cur]);
        }

    }

    // n中取k组合，去重
    int combinationUnique(vector<int>& v, int k) {
        this->data = v;
        cnt = 0;

        sort(v.begin(), v.end());

        combinationUnique(0,0,k);

        return cnt;
    }

    void combinationUnique(int cur, int lower, int k) {
        // 下一个元素从[lower,$]中选
        if (cur == k) {
            if (show)
                printV(data, k);
            cnt ++; // 一个组合
            return;
        }

        if (lower > data.size())
            return;
        
        for (int i = lower ; i < data.size() ; i++) {
            if (i > lower && comWillRepeat(i, lower))
                continue;
            /*
            if (i > lower && data[i] == data[lower])
                continue;
                */
            swap(data[i], data[cur]);
            combinationUnique(cur+1, i+1, k);
            swap(data[i], data[cur]);
        }

    }
    bool comWillRepeat(int i, int lower) {
        for (int m = lower ; m < i ; m++) {
            if (data[m] == data[i]) {
                return true;
            }
        }
        return false;
    }

    void printV(vector<int>& v) {
        printV(v, v.size());
    }

    void printV(vector<int>& v, int k) {
        cout<<"[";
        for (int i = 0 ; i < k ; i++) {
            cout<<v[i];
            if (i != k-1) {
                cout<<", ";
            }
        }
        cout<<"]\n";
    }
};
